1861E - Non-Intersecting Subpermutations - CodeForces Solution

/*--  Le Festin  --*/
#include "bits/stdc++.h"
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// */

using namespace std;

/*
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> 
// */

typedef long long ll;
typedef long double ld;

#define pb push_back 
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define lb(v,x) lower_bound(v.begin(),v.end(),x)
#define ub(v,x) upper_bound(v.begin(),v.end(),x)
#define mp make_pair
#define vii vector < ll >
#define dt cout<<"HERE\n";
#define pii pair < ll , ll >
#define viii vector< vii > 
#define vpi vector < pii >
#define fi first
#define se second 
#define sz(x) ((ll)x.size())
#define len(x) ((ll)x.length())
 
const ll inf=1e18;
//const ll mod =8589934592;
using cd= complex < double > ;
// ll mod=1e18;
ll mod = 998244353;
//ll mod=1e9+7;
ll modInverse(ll a,ll m){ll m0=m;ll y=0,x=1;if(m == 1)return 0;while(a> 1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}  
ll powm(ll a,ll b){a=a%mod;ll res=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return (res%mod);}
void up(vector< char>  &v){ for ( ll i=0;i<sz(v);i++) cout<<v[i]<<' '; cout<<'\n'; }
void up( vii &v) { for ( auto i: v) cout<<i<<' '; cout<<'\n';}
void up( vpi &v) { for ( auto i: v) cout<<i.fi<<' '<<i.se<<'\n';}
void up( viii &v) { for ( auto i: v) { for ( auto j: i) cout<<j<<' '; cout<<'\n';}}


const ll N=3e4+3;
ll arr[N];
void fac(){
    arr[0]=1;
    for ( ll i=1;i<N;i++)
        arr[i]=arr[i-1]*i%mod;
}
ll f(ll i){
    return arr[i];
}

void solve(){
    
    ll n,k;
    cin>>n>>k;
    ll tot=0;
    ll mot=f(k)*powm(k,n-k)%mod;

    vii dp(n);
    
    for ( ll i=k-1;i<n;i++){
        if ( i==k-1){
            dp[i]=mot;
        }
        else{
            dp[i]=mot;
            ll p=1;
            for ( ll j=i-1;j>max(k-2,i-k);j--){
                ll val=(dp[j]*modInverse(powm( k,p),mod))%mod*f(p)%mod;
                p++;
                dp[i]-=val;
                if ( dp[i]<0)
                    dp[i]+=mod;
            }
        }
    
        tot+=dp[i];
        tot%=mod;
    }

    cout<<tot<<'\n';


}

int main(){
 //   /*
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

//  /*
    #ifndef ONLINE_JUDGE
        freopen("INPUT.txt","r",stdin);
        freopen("OUTPUT.txt","w",stdout);
    #endif
//  */




    fac();
    ll t=1;
   // cin>>t;
    for ( ll i=1;i<=t;i++)
        solve();
  //  cout << clock() / double(CLOCKS_PER_SEC) << endl;
}